/*
 * Solver.hpp
 *
 *  Created on: 10 déc. 2011
 *      Author: Elca
 */

#ifndef SOLVER_HPP_
#define SOLVER_HPP_

#include "def.hpp"
#include "BoardInfos.hpp"
#include <list>
#include <cstring>
#include <set>
#include <Hash.hpp>
using namespace  std;

namespace pcm {

class comp_BoardInfos {
public:
    bool operator()(BoardInfos *c1, BoardInfos *c2) const
    {
    	return (c1->board() < c2->board());
    }
};

class Solver {
public:
	Solver();
	virtual ~Solver();

	list<BoardInfos*> m_boardToProcess;
	//set<BoardInfos*,comp_BoardInfos >  m_boardDiscovered;
	Hash m_boardDiscovered;
	LL m_solutions;

//	inline void cleanMemory(BoardInfos* _boardInfos,int& _numberPegPrev){
//		if(_boardInfos->numberPeg()<_numberPegPrev){
//
//			set<BoardInfos*,comp_BoardInfos >::iterator it = m_boardDiscovered.begin();
//			LL numberBoard= 0;
//			while(it!=m_boardDiscovered.end()){
//				if((*it)->numberPeg()==_numberPegPrev){
//					numberBoard++;
//					BoardInfos* tmp = *it;
//					m_boardDiscovered.erase(it++);
//					delete tmp;
//				}else{
//					it++;
//				}
//			}
//			cout<<_boardInfos->numberPeg()<<" n:"<<numberBoard<<endl;
//			_numberPegPrev=_boardInfos->numberPeg();
//		}
//	}

	inline void executeMove(BoardInfos* _boardInfos,HoleJump & jump){
		BoardInfos newBoardInfos = _boardInfos->applyMoveStack(jump);
		//Is in hash
		//#pragma omp critical
		{
			BoardInfos* existingBoardInfos = m_boardDiscovered.getItem(newBoardInfos.board());
			if(existingBoardInfos == NULL){
				BoardInfos *n = new BoardInfos(&newBoardInfos);
				m_boardDiscovered.add(n);
				//Add to process
				m_boardToProcess.push_back(n);
			}else{
				existingBoardInfos->incrementNumberJoin(_boardInfos->numberJoin());
			}
//			set<BoardInfos*,comp_BoardInfos >::iterator existingBoardInfos = m_boardDiscovered.find(&newBoardInfos);
//			if(existingBoardInfos==m_boardDiscovered.end()){
//				//Add to hash
//				BoardInfos *n = new BoardInfos(&newBoardInfos);
//				m_boardDiscovered.insert(n);
//				//Add to process
//				m_boardToProcess.push_back(n);
//			}else{
//				(*existingBoardInfos)->incrementNumberJoin(_boardInfos->numberJoin());
//			}
		}
	}

	void solve(BoardInfos &board){
		m_solutions= 0;
		BoardInfos* startBoard = new BoardInfos(&board);

		m_boardDiscovered.add(startBoard);
		m_boardToProcess.push_back(startBoard);
		int numberPegPrev= startBoard->numberPeg();

		//#pragma omp parallel
		{
			//#pragma omp single
			{

				do{
					BoardInfos* currBoardInfos = NULL;
				//	#pragma omp critical
					{

					currBoardInfos = m_boardToProcess.front();
					m_boardToProcess.pop_front();
					}
					//Cleaning numberpeg sup
					//cleanMemory(currBoardInfos,numberPegPrev);

					//Find moves
					if((currBoardInfos->numberPeg()+currBoardInfos->numberPeg()) > BoardInfos::gameNumberHole()){ //TODO: Looking for better multiplication
						//Find empty hole
						for(int iHole=0;iHole<BoardInfos::gameNumberHole();iHole++){
							bool hole = currBoardInfos->hole(iHole);
							if(!hole){
								vector<HoleJump> jumps= currBoardInfos->endlHoleJumps(iHole);
								for(size_t iJump=0;iJump<jumps.size();iJump++){
									//Is a correct move
									if(currBoardInfos->hole(jumps[iJump].start()) && currBoardInfos->hole(jumps[iJump].jump())){
										//#pragma omp task
											executeMove(currBoardInfos,jumps[iJump]);
									}
								}
							}
						}
					}else{
						//Find oo. pattern
						for(int iHole=0;iHole<BoardInfos::gameNumberHole();iHole++){
							bool hole = currBoardInfos->hole(iHole);
							if(hole){
								vector<HoleJump> jumps= currBoardInfos->startHoleJumps(iHole);
								for(size_t iJump=0;iJump<jumps.size();iJump++){
									//Is a correct move
									if( currBoardInfos->hole(jumps[iJump].jump()) && !currBoardInfos->hole(jumps[iJump].end())){
										if(currBoardInfos->numberPeg()>2){
											//#pragma omp task
												executeMove(currBoardInfos,jumps[iJump]);
										}else{
											m_solutions+= currBoardInfos->numberJoin();
										}
									}
								}
							}
						}
					}
				}while(!m_boardToProcess.empty());
			}
		}
		cout<<"Number solutions: "<<m_solutions<<endl;

		//Delete hash
		set<BoardInfos*,comp_BoardInfos >::iterator it;
//		for(it=m_boardDiscovered.begin();it!=m_boardDiscovered.end();it++){
//			delete (*it);
//		}
//		m_boardDiscovered.clear();
	}
};

} /* namespace pcm */
#endif /* SOLVER_H_ */
